package 每日一题;

import com.alibaba.fastjson.JSON;

import java.util.Arrays;
import java.util.Random;

public class No480滑动窗口中位数 {

    /**
     * 中位数是有序序列最中间的那个数。如果序列的长度是偶数，则没有最中间的数；
     * 此时中位数是最中间的两个数的平均数。
     * 例如：
     * [2,3,4]，中位数是 3
     * [2,3]，中位数是 (2 + 3) / 2 = 2.5
     * 给你一个数组 nums，有一个长度为 k 的窗口从最左端滑动到最右端。
     * 窗口中有 k 个数，每次窗口向右移动 1 位。
     * 你的任务是找出每次窗口移动后得到的新窗口中元素的中位数，并输出由它们组成的数组。
     *  
     *
     * 示例：
     * 给出 nums = [1,3,-1,-3,5,3,6,7]，以及 k = 3。
     * 窗口位置                      中位数
     * ---------------               -----
     * [1  3  -1] -3  5  3  6  7       1
     *  1 [3  -1  -3] 5  3  6  7      -1
     *  1  3 [-1  -3  5] 3  6  7      -1
     *  1  3  -1 [-3  5  3] 6  7       3
     *  1  3  -1  -3 [5  3  6] 7       5
     *  1  3  -1  -3  5 [3  6  7]      6
     *  因此，返回该滑动窗口的中位数数组 [1,-1,-1,3,5,6]。
     */

    public double[] medianSlidingWindow(int[] nums, int k) {

        int[] arr=new int[k];
        for (int i = 0; i < k; i++) {
            arr[i]=nums[i];
        }
        fastSort(arr);
        double[] result=new double[nums.length-k+1];

        for (int i = 0; i < result.length; i++) {

            //i+k
            //存入中位数
            if(k%2==0) {
                //偶数个,兼顾两个 除2再加,避免溢出
                result[i] = arr[arr.length/2]/2.0+arr[arr.length/2-1]/2.0;
            }else{
                //奇数个,直接除2即可
                result[i] = arr[arr.length/2];
            }
            //arr中是排好序的,所以要找到它的下标
            int indexByBinarySearch = getIndexByBinarySearch(arr, nums[i]);
            if(i+k<nums.length) {
                arr[indexByBinarySearch] = nums[i + k];
                //维护好放进去的元素
                bubblingSort(arr, indexByBinarySearch);
            }
        }

        return result;
    }

    //手写一个快排
    public void fastSort(int[] arr){
        //反射着来
        MyFastSort myFastSort=null;
        try {
            myFastSort = MyFastSort.class.newInstance();
        } catch (InstantiationException | IllegalAccessException e) {
            e.printStackTrace();
        }
        assert myFastSort != null;
        myFastSort.fastSort(arr);
    }

    //再写一个二分查找排好序的数组指定元素下标
    public int getIndexByBinarySearch(int[] arr,int target){

        int left=0;
        int right=arr.length-1;

        while (left<=right){

            int mid=(right-left)/2+left;

            if(arr[mid]>target){
                //中间的元素大于目标元素,去左边
                right=mid-1;
            }else if(arr[mid]<target){
                //中间的元素小于目标元素,去右边
                left=mid+1;
            }else{
                return mid;
            }
        }

        return -1;
    }

    //再写一个冒泡排序(仅一个元素) 因为是一个元素放入排好序的数组中,所以分为向左冒泡,或者向右冒泡
    public void bubblingSort(int[] arr, int index){

        //冒泡排序无需左右游标,直接+1,-1即可

        //情况1:当前大了,向右冒泡
        while (index+1<arr.length&&arr[index]>arr[index+1]){
            int temp=arr[index];
            arr[index]=arr[index+1];
            arr[index+1]=temp;
            index++;
        }

        //情况2:当前小了,向左冒泡
        while (index > 0 && arr[index]<arr[index-1]){
            int temp=arr[index];
            arr[index]=arr[index-1];
            arr[index-1]=temp;
            index--;
        }
    }

    public static void main(String[] args) {
        No480滑动窗口中位数 n=new No480滑动窗口中位数();
        int[] arr={5,2,2,7,3,7,9,0,2,3};
        double[] result = n.medianSlidingWindow(arr, 9);
        System.out.println(JSON.toJSONString(result));
    }

}

class MyFastSort{

    public MyFastSort() {
    }

    public void fastSort(int[] arr){
        sortDg(arr,0,arr.length-1);
    }

    //递归进行排序
    private void sortDg(int[] arr,int left,int right){

        if(left>=right){
            return;
        }

        //随机的基点
        Random random=new Random();
        int randomIndex=random.nextInt(right-left)+left;
        int temp=arr[randomIndex];
        arr[randomIndex]=arr[left];
        arr[left]=temp;

        //进行交换
        int midIndex = getMidBig(arr, left, right);
        //左
        sortDg(arr,left,midIndex-1);
        //右
        sortDg(arr,midIndex+1,right);
    }

    //中间排序,返回中间大的下标
    private int getMidBig(int[] arr,int left,int right){
        //基点
        int tmp=arr[left];
        while (left<right){
            //先从右边找到一个小于基点的
            while (left<right&&arr[right]>=tmp){
                right--;
            }
            //将小的放到右边去
            arr[left]=arr[right];
            //再从左边找到一个大于基点的
            while (left<right&&arr[left]<=tmp){
                left++;
            }
            arr[right]=arr[left];
        }
        //出来后,就是left==right,放回基点,返回基点下标
        arr[left]=tmp;
        return left;
    }



}
